package MyUtils;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class MHMoban {

    /*
        全排列 可指定长度k
     */
    static int[] nums;
    static boolean[] vis;

    static List<List<Integer>> res = new ArrayList<>();
    static List<Integer> tmp = new ArrayList<>();

    public static List<List<Integer>> quanPaiLie(int[] p, int step){
        nums = p;
        vis = new boolean[nums.length];
        int k = step;
        bacTrck(k);
        return res;
    }

    private static void bacTrck(int k) {
        if (tmp.size() == k) {
            res.add(new ArrayList<>(tmp));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (vis[i]) {
                continue;
            }
            tmp.add(nums[i]);
            vis[i] = true;
            bacTrck(k);
            tmp.remove(tmp.size()-1);
            vis[i] = false;
        }
    }

    /*
        子集
     */
    static int[] p;

    static public List<List<Integer>> ziji(int[] nums) {
        p = nums;

        int cI = 0; // 子集背一下是cI
        bakT(cI);
        res.add(new ArrayList<>()); // 空[]
        return res;
    }

    static private void bakT(int cI) {
        if(cI == p.length){
            return;
        }

        for (int i = cI; i < p.length; i++) {
            tmp.add(p[i]);
            res.add(new ArrayList<>(tmp));
            bakT(i+1);
            tmp.remove(tmp.size()-1);
        }
    }

    /*
        coushu_wuxian_minGeshu
     */
    public int coushu_wuxian_minGeshu(int[] p, int tar) {
        int[][] dp = new int[p.length+1][tar+1];
        for (int j = 1; j <= tar; j++) {
            dp[0][j] =  999;
        }
        for (int pN = 1; pN <= p.length; pN++) {
            for (int cS = 1; cS <= tar; cS++) {
                int cI = pN-1;
                int na = 999; // 1
                if(cS-p[cI]>=0) {
                    na = dp[pN][cS - p[cI]] + 1; // 2 pN不-1
                }
                int buna = dp[pN - 1][cS]; // 3 不拿就是不拿 -> 选择范缩
                dp[pN][cS] = Math.min(na,buna);
            }
        }
        return dp[p.length][tar]==999?-1:dp[p.length][tar]; // 4
    }
}
